|
The K shortest path routing algorithm is an extension algorithm of the shortest path routing algorithm in a given network. It is sometimes crucial to have more than one path between two nodes in a given network. In the event there are additional constraints, other paths different from the shortest path can be computed. To find the shortest path one can use shortest path algorithms such as Dijkstra’s algorithm or Bellman Ford algorithm and extend them to find more than one path. The K Shortest path routing algorithm is a generalization of the shortest path problem. The algorithm not only finds the shortest path, but also K-1 other paths in order of increasing cost. K is the number of shortest paths to find. The problem can be restricted to have the K shortest path without loops (loopless K shortest path) or with loop. == History == Since 1957 there have been many papers published on the K Shortest path routing algorithm problem. Most of the fundamental works on not just finding the single shortest path between a pair of nodes, but instead listing a sequence of the K shortest paths, were done between the 1960s and up to 2001. Since then, most of the recent research has been about the applications of the algorithm and its variants. In 2010, Michael Gunter et al. published a book on ''Symbolic calculation of K-shortest paths and related measures with the stochastic process algebra tool CASPA''.〔Michael Günther et al.: “Symbolic calculation of K-shortest paths and related measures with the stochastic process algebra tool CASPA”. In: Int’l Workshop on Dynamic Aspects in Dependability Models for Fault-Tolerant Systems (DYADEM-FTS), ACM Press (2010) 13–18.〕 Important works on the K Shortest path problem: The (BibTeX database ) contains more articles. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「K shortest path routing」の詳細全文を読む スポンサード リンク
|